The various modes relating to the present invention relate to a lock management system, a lock management method and a lock management program in a multiprocessor system.
In a computer system, a plurality of processes and threads are generally run in parallel in order to make efficient use of computer resources, such as a processor. Although processes and threads are not strictly the same, they are similar concepts in meaning a unit of program execution, and therefore, in the description given below, all of the units of program execution are called threads.
In an information system which is composed in such a manner that a plurality of threads are executed simultaneously in parallel by having a plurality of processors, there are cases where a plurality of threads, in parallel, access data which is located in a memory. If the data that is accessed by the respective threads is mutually independent, then there is no problem if the plurality of threads access in parallel in the memory. However, if a plurality of threads access related data, or the same data, without being aware of the other thread(s), then there may be cases where a different result is obtained to a case where the data is accessed by a single thread.
For example, it is possible to envisage an operation in which two threads increment the same variable by 1, in other words, an operation in which both threads read out the variable, increment the variable by 1 and then write back the result. If two threads are executed in a sequence in which a second thread carries out processing for incrementing the variable by 1 after a first thread has completed processing for incrementing the variable by 1, then the value of the variable is incremented by 2. Considering the processing contents of the threads, this is a correct result. On the other hand, if the two threads are executed in parallel, then processing may be executed in a sequence by which, for example, the second thread reads out the variable after the first thread has read out the variable and before the first thread has written back a result incremented by 1. If the processing advances according to this sequence, then both threads rewrite the variable as the initial value incremented by 1, without being aware of the updating of the variable by the other thread, and therefore the value of the variable is incremented by 1 only, despite the fact that there are two threads which have carried out processing for incrementing the variable by 1. In other words, a correct result is not obtained in this case.
A processing time period where a problem occurs if processing of one thread is carried out during the processing of another thread (in the example described above, the time period from the thread reading out the data until writing back the value of the processing result) is called a “critical session”. In order to obtain a correct processing result, it is necessary to implement explicit control so that there is no interrupt of processing of one thread, while another thread is executing processing in a critical session.
Apart from the simplest mode of a critical session in which only one thread can be executed, there are also critical sessions in which the number of executable threads is limited, and critical sessions which have two types of lock mode, namely, an exclusive lock (write lock) and a shared lock (read lock). A critical session in which the number of executable threads is limited can be understood as a critical session in which only one thread can be executed, which is generalized on the basis of the upper limit of the number of executable threads. In a critical session which has a shared lock and an exclusive lock, the number of threads that can acquire an exclusive lock and execute critical session processing is limited to 1, whereas with a shared lock, there is no limit of the number of threads that can be executed simultaneously and threads can acquire a shared lock and execute critical session processing, provided that there is no thread that has acquired an exclusive lock.
Furthermore, as an extension of a critical session having a shared lock and an exclusive lock, there are also lock modes in which a plurality of lock modes are prepared and the number of threads which can coexist in respective modes is specified. Non-Patent Document 1 discloses one example of a complex lock of this kind. In the method described in Non-Patent Document 1, eight lock modes are specified: “ACCESS SHARE”, “ROW SHARE”, “ROW EXCLUSIVE”, “SHARE UPDATE EXCLUSIVE”, “SHARE”, SHARE ROW EXCLUSIVE″, “EXCLUSIVE”, “ACCESS EXCLUSIVE”. The relationships between the (non-conflicting) lock modes which can be executed simultaneously and the (conflicting) lock modes which cannot be executed simultaneously are specified in each lock mode in Table 13-2. In a locking method which has a plurality of modes of this kind, the locks of various modes can be handled in an integrated fashion by specifying conflict relationship table.
In a multiprocessor system having a plurality of processors, a general method for achieving a critical session uses flags (called “lock words” below) to indicate whether or not there exists a process which is currently executing a critical session. In the case of the simplest lock, a thread which is seeking to enter a critical session firstly confirms the lock word, and if the lock word is a value indicating out-of-use (called “unlock” below), then the thread changes the lock word to a value indicating in-use (called “locked” below) and executes critical session processing. On the other hand, if the confirmed lock mode is “locked”, then the thread waits for that lock word to become “unlocked”, and then changes the lock word to “locked” and executes critical session processing. Furthermore, when the thread has completed the execution of the critical session, the thread carries out a process for returning the lock word to “unlocked”. By control of this kind, it is possible to avoid the occurrence of a problem where a thread executed by one processor executes a critical session simultaneously with a thread executed by another processor (where the processes conflict).
In the case of a locking method in which there are two types of lock mode, namely, an exclusive lock and a shared lock, the lock status can be expressed by: (1) one bit which indicates whether or not there is a thread which is executing a critical session by having acquired an exclusive lock, and (2) a plurality of bits indicating the number of threads which are executing a critical session by having acquired a shared lock (the number of bits capable of expressing the maximum number of threads). If these two types of information can fall within one word that can be handled by an indivisible (atomic) access command of the processor, then this locking method can be achieved by using this command.
One example of an indivisible (atomic) access command is a cmpxchg command which has been created for Intel x86 processors (see Non-Patent Document 2). The cmpxchg command is a command that uses three operands: a register (eax register) reserved by the command, a register operand, and a memory operand. Consequently, the cmpxchg command indivisibly carries out a series of operations: (1) reading in the value of the memory operand to the processor; (2-1) writing the value of the register operand to the memory if the value of the memory operand matches the value in the eax register; and (2-2) writing the value of the memory operand to the eax register if the value does not match the value in the eax register. Here, “indivisibly” means that it is guaranteed by a hardware operation that another processor will not access the memory during the memory writing operation in (1) and the memory writing operation in (2-1).
Furthermore, it is possible to determine which of (2-1) and (2-2) has been executed by the cmpxchg command by investigating whether or not the value in the eax register after executing a CAS command has changed compared to the value before executing the command. This operation performed by the cmpxchg command is called “CAS” (Compare And Swap) below. Apart from the CAS operation, the indivisible (atomic) commands of the processor include a command for reading out one word in the memory, applying the four arithmetic operators or a logic calculation, and then writing the result to the same memory position. With this indivisible calculation command, it is guaranteed that memory access will not be performed by another processor between the initial memory reading operation and the operation for writing the calculation result to the memory.
The method for achieving a locking method having lock modes of two types, namely, an exclusive lock and a shared lock using a CAS operation is as described below. The thread which is seeking to acquire a lock firstly reads in the lock word and then investigates whether or not a lock conflicting with the lock of the mode that the thread is seeking to acquire has been acquired. More specifically, it is confirmed that (1) there is no thread that has already acquired both an exclusive lock and a shared lock, if the mode that the thread is seeking to acquire is an exclusive lock, and that (2) there is no thread that has acquired an exclusive lock, if the mode that the thread is seeking to acquire is a shared lock. If, as a result of this, a lock conflicting with the lock of the mode that the thread is seeking to acquire has not been acquired, then a CAS operation may be performed in respect of the lock word, by setting the lock word in a state where the lock of the mode that the thread is seeking to acquire has been acquired, as the new value, and setting the value of the lock word read out in the previous operation, as the old value.
Here, the specific value of the new value is: (1) a value setting one bit that indicates whether or not there is a thread that has acquired an exclusive lock, from among the lock words, and is executing a critical session, if the mode that the thread is seeking to acquire is an exclusive lock; and (2) a value obtained by incrementing by 1 the number represented by the plurality of bits indicating the value of the threads which have acquired a shared lock, from among the lock words, and are executing a critical session, if the mode that the thread is seeking to acquire is a shared lock. Thereupon, if the CAS operation described above is successful, then that thread successfully acquires a lock, and starts to execute a critical session. If this CAS operation fails, then the value of the lock word read out in the CAS operation is set as the old value and the procedure is carried out again from the beginning. Furthermore, if, as a result of investigating the lock word that has been read out, a lock has been acquired which conflicts with the lock of the mode that the thread is seeking to acquire, then a wait is performed until this conflicting lock is released.
As described above, in all of the specified lock modes, if the number of threads that have acquired a lock in the modes can be expressed by one word which can be handled by an indivisible access command of the processor, then it is possible to achieve a lock acquisition operation by a simple format of reading out the word and then performing a CAS access.
On the other hand, in a case of a locking method in which a plurality of lock modes are prepared and the number of threads that can coexist between the modes is specified, then, in all of the specified lock modes, the number of threads that have acquired a lock in the modes cannot be expressed by one word which can be handled by an indivisible access command of the processor, and therefore it is not possible to achieve a lock acquisition operation by a simple format such as that described above.
In this way, for all of the specified lock modes, a sequence holding the number of threads that have acquired a lock in those modes, and a mechanism for exclusively controlling access to that sequence (called a “mutex” below) are prepared. With this scheme, a thread acquiring a lock firstly acquires a mutex, and then determines whether or not a lock can be acquired by accessing the sequence. If, as a result of this, a lock can be acquired, then the lock acquisition operation is achieved by adding one to the sequence elements corresponding to the lock mode, and then releasing the mutex.    Non-Patent Document 1: PostqreSQL 9.0.7 Documentation Chapter 13 Concurrency Control [online]; [retrieved May 11, 2000]; Internet <URL: http//www.postgresql.org/docs/9.0/static/explicit-locking-html>    Non-Patent Document 2: Intel® 64 and IA-32 Architectures Software Developer's Manual Volume 2A [online]; [retrieved May 11, 2000]; Internet <URL: http://www.intel.com/Assets/PDF/manual/253666.pdf>